package com.wenhao.leetcode.medium;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 题目：https://leetcode-cn.com/problems/remove-k-digits/
 * 移掉 K 位数字
 *
 * @author Wenhao Tong
 * @create 2021-07-09 15:09
 */
public class LeetCode402 {
    public static void main(String[] args) {
        LeetCode402 leetCode402 = new LeetCode402();
        String s = leetCode402.removeKdigits("10200", 1);
        System.out.println(s);
    }

    public String removeKdigits(String num, int k) {
        Deque<Character> deque = new LinkedList<>();
        int count = 0;
        int i = 0;
        while (i < num.length()) {
            while (count < k && deque.size() > 0 && num.charAt(i) < deque.peek()) {
                deque.pop();
                count++;
            }
            deque.push(num.charAt(i));
            i++;
        }
        StringBuilder result = new StringBuilder();
        while (deque.size() > 0 && result.length() < num.length() - k) {
            result.append(deque.pollLast());
        }
        result.append(num.substring(i));
        if (result.length() == 0) {
            return "0";
        }
        return result.toString().replaceAll("^(0+)", "");
    }
}
